#include<iostream>
#include<vector>
#include<string>
using namespace std;

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int len1 = text1.size();
        int len2 = text2.size();
        vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
        for (int i = 0; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                if (text1[i] == text2[j]) {
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                }
                else {
                    dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
                }
            }
        }
        return dp[len1][len2];
    }
};

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int len1 = nums1.size();
        int len2 = nums2.size();
        vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1));
        for (int i = 0; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                if (nums1[i] == nums2[j]) {
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                }
                else {
                    dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
                }
            }
        }
        return dp[len1][len2];
    }
};

class Solution {
public:
    int numDistinct(string s, string t) {
        int len1 = s.size();
        int len2 = t.size();
        vector<vector<long long>> dp(len1 + 1, vector<long long>(len2 + 1));
        // dp[0].clear();dp[0].resize(len2, 1);
        for (int i = 0; i < len1; i++) dp[i][0] = 1;
        for (int i = 0; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                if (s[i] == t[j]) {
                    dp[i + 1][j + 1] = (dp[i][j] + dp[i][j + 1]) % 1000000007;;
                }
                else {
                    dp[i + 1][j + 1] = dp[i][j + 1] % 1000000007;
                }
            }
        }
        // for(int i = 0;i <= len1;i++){
        //     for(int j = 0;j <= len2;j++){
        //         cout << dp[i][j] << " ";
        //     }
        //     cout << endl;
        // }
        return dp[len1][len2];
    }
};

class Solution {
public:
    bool isMatch(string s, string p) {
        if (s.size() == 0 && p.size() == 0) return true;
        if (s.size() == 0 && p.size() == 1 && p[0] == '?') return false;
        if (s.size() == 0) s += ' ';
        int len1 = s.size();
        int len2 = p.size();
        vector<vector<bool>> dp(len1 + 1, vector<bool>(len2 + 1));
        dp[0][0] = true;

        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (s[i - 1] == p[j - 1] || p[j - 1] == '?') {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                else if (p[j - 1] == '*' && dp[i - 1][j - 1]) {
                    dp[0][j] = true;
                    for (int k = i; k <= len1; k++)
                        dp[k][j] = true;
                }
            }
        }
        for (int i = 0; i <= len1; i++) {
            for (int j = 0; j <= len2; j++) {
                cout << dp[i][j] << " ";
            }
            cout << endl;
        }
        if (len2 > 0 && dp[len1][len2] == false && p[len2 - 1] == '*') {
            len2--;
        }
        return dp[len1][len2];
    }
};

class Solution {
public:
    bool isMatch(string s, string p) {
        int len1 = s.size();
        int len2 = p.size();
        vector<vector<bool>> dp(len1 + 1, vector<bool>(len2 + 1));
        dp[0][0] = true;
        for (int i = 0; i < len2; i++) {
            if (p[i] == '*') {
                dp[0][i + 1] = true;
            }
            else break;
        }

        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (s[i - 1] == p[j - 1] || p[j - 1] == '?') {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                else if (p[j - 1] == '*') {
                    // dp[0][j] = true;
                    // for(int k = i;k >= 0;k--){
                    //     if(dp[k][j - 1]){
                    //         dp[i][j] = true;
                    //         break;
                    //     }
                    // }
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                }
            }
        }
        // for (int i = 0; i <= len1; i++) {
        //     for (int j = 0; j <= len2; j++) {
        //         cout << dp[i][j] << " ";
        //     }
        //     cout << endl;
        // }
        if (len2 > 0 && dp[len1][len2] == false && p[len2 - 1] == '*') {
            len2--;
        }
        return dp[len1][len2];
    }
};

class Solution {
public:
    bool isMatch(string s, string p) {
        int len1 = s.size();
        int len2 = p.size();
        vector<vector<bool>> dp(len1 + 1, vector<bool>(len2));
        dp[0][0] = true;
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (s[i - 1] == p[j - 1] || p[j - 1] == '.') {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                else if (p[j - 1] == '*') {
                    if (p[j - 2] == '.')
                        dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                    else {
                        int flag = 1;
                        for (int k = j - 1; k < i; k++) {
                            if (p[j - 2] != s[k]) {
                                flag = 0;
                            }
                        }
                        dp[i][j] = dp[i][j - 1] || (flag && dp[i - 1][j]);
                    }
                }
            }
        }
        for (int i = 0; i <= len1; i++) {
            for (int j = 0; j <= len2; j++) {
                cout << dp[i][j] << " ";
            }
            cout << endl;
        }
        return dp[len1][len2];
    }
};

class Solution {
public:
    bool isMatch(string s, string p) {
        int len1 = s.size();
        int len2 = p.size();
        vector<vector<bool>> dp(len1 + 1, vector<bool>(len2 + 1));
        dp[0][0] = true;
        for (int i = 1; i < len2; i += 2) {
            if (p[i] == '*') {
                dp[0][i + 1] = true;
            }
            else break;
        }
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (s[i - 1] == p[j - 1] || p[j - 1] == '.') {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                else if (p[j - 1] == '*') {
                    // if (p[j - 2] == '.'){
                    //     dp[i][j] = dp[i - 1][j] || dp[i][j - 2];
                    // }
                    // else {
                    //     dp[i][j] = (p[j - 2] == s[i - 1] && dp[i - 1][j]) || dp[i][j - 2];
                    // }
                    dp[i][j] = dp[i][j - 2] || (p[j - 2] == '.' || p[j - 2] == s[i - 1]) && dp[i - 1][j];
                }
            }
        }
        // for (int i = 0; i <= len1; i++) {
        //     for (int j = 0; j <= len2; j++) {
        //         cout << dp[i][j] << " ";
        //     }
        //     cout << endl;
        // }
        return dp[len1][len2];
    }
};

